A variety of algorithms have been developed to decode Reed-Solomon codes. A typical decoding procedure consists of the following steps:
1. Computation of the Syndrome Polynomial. PA0 2. Determination of the Error Locator Polynomial, .LAMBDA.(x), and the Error Magnitude Polynomial, .OMEGA.(x). PA0 3. Calculation of the Error Magnitudes and Error Locations. PA0 4. Substraction of the Errors from the received message if correctable.
A Reed-Solomon Code is defined in terms of its generator polynomial, G(x): ##EQU1## where m.sub.0 is an integer, and .beta. is a field element in GF (q.sup.m). t is the designed symbol error correcting capacity of the code. While the selection of m.sub.0 is completely arbitrary, .beta. must be chosen such that the factors of G(x) do not form a subfield in GF(q.sup.m). In other words, if .beta.=.alpha. , where .alpha. is a primitive element in GF(q.sup.m) and is an integer, then must not contain factors in common with q.sup.m -1.
The coding process may be viewed as any method of taking a sequence of .kappa. message symbols, represented as the coefficients of an order .kappa.-1 polynomial, and appending 2t redundancy symbols to create a code block, C(x). The redundancy symbols are chosen such that the roots of C(x) include the roots of G(x). Mathematically, this may be described as follows: EQU C(x)=x.sup.2t M(x)+R.sub.G(x) [x.sup.2t M(x)]=A(x)G(x) (2)
It should be noted here that the above relationships portray the construction of a systematic code. Any invertible transformation that maps M(x) into C(x) such the G(x) divides C(x) can be viewed as an encoding transformation. The process of corrupting the original code block, C(x), with errors may be viewed as adding an error polynomial, E(x), to C(x). The resultant, corrupted polynomial is known as the received polynomial, R(x): EQU R(x)=C(x)+E(x)=A(x)G(x)+E(x) (3)
The .nu. non-zero terms of the error polynomial contain all the information necessary to completely reconstruct the original C(x), since each term corresponds to a symbol error location and magnitude: ##EQU2## where j.sub..kappa. is the location of the .kappa..sup.th error and e.sub.j.sbsb.k is the magnitude of the error. The complete syndrome polynomial, S(x), is obtained by evaluating the error polynomial, E(x), at all field elements, starting with the roots of G(x): ##EQU3##
S(x) may be viewed as a transform of E(x) into the frequency domain. S(x) completely determines E(x). From Equation 3 it can be seen that the first 2t terms of S(x) may be determined by evaluating the received polynomial, R(x), at the roots of G(x): ##EQU4## where the mod x.sup.2t indicates that only the first 2t terms of S(x) are correctly predicted by this expression. It is also easily shown that if E(x) contains .nu. non-zero terms, that S(x) may be written: ##EQU5## where all quantities are as defined for Equation 4. Retaining only the first 2t terms and combining with Equation 6: ##EQU6##
Hence, all syndrome polynomials, S(x), which can be written in the above form with some .nu..ltoreq.t correspond to correctable error patterns. Those which cannot be so expressed correspond to uncorrectable error patterns.
FIG. 1 shows a graphical way of considering this problem. For a given Galois Field, the circles 22A through 22F represent the domains of correctable errors for the properly encoded polynomials 20A through 20F. If the correctly transmitted polynomial 20C is received as 20C, there is no error to be corrected. If R(X)1 is received, the error is properly correctable to 20C. If R(X)2 is received, the error is improperly correctable to 20A. If R(X)3 is received, the error is uncorrectable.
If an error is uncorrectable it is desireable for the user to know that the data is corrupted and cannot be corrected. However, no Reed-Solomon decoder has been designed which determines whether the received polynomial is correctable.